from typing import List

MODE = int(1e9+7)
class Solution:
    def magicalSum(self, m: int, k: int, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()

        # 从n个里选m个使恰好有k个不重复
        def dfs(idx, cnt, used:set[int],product):
            if cnt == m:
                if len(used) == k:
                    return product
                else:
                    return 0
            if len(used) > k or cnt > m or idx >= n: return 0
            ans = 0
            for j in range( n):
                # if j == idx: continue
                if nums[j] in used:
                    res = dfs(j, cnt + 1, used,product*nums[j])
                else:
                    used.add(nums[j])
                    res = dfs(j, cnt + 1, used,product*nums[j])
                    used.remove(nums[j])
                ans += res
                ans %= MODE
            return ans
        result = 0
        for i in range(n):
            result += dfs(i, 1, {nums[i]},nums[i])
            result %= MODE
        return result

if __name__ == '__main__':
    s = Solution()
    r = s.magicalSum( 2,1,[63])
    print(r)
